package alo.p5;
//基于动态循环数组实现队列
public class DynArrayQueue {
    private int front;
    private int rear;
    private int capacity;
    private int[] array;
    private DynArrayQueue(){
        capacity=1;
        front=-1;
        rear=-1;
        array=new int[1];
    }
    private static DynArrayQueue createQueue(int size){
        return new DynArrayQueue();
    }
    public boolean isEmpty(){
        return (front==-1);
    }
    public boolean isFull(){
        return (rear+1)%capacity==front;
    }
    public int getQueueSize(){
        if (front==-1) return 0;
        int size=(capacity-front+rear+1)%capacity;
        if (size==0){
            return capacity;
        }else return size;
    }
    //数组扩增
    public void resizeQueu(){
        int initCapacity=capacity;
        capacity*=2;
        int[] oldArray=array;
        array=new int[this.capacity];
        for (int i=0;i<oldArray.length;i++){
            array[i]= oldArray[i];
        }
        //起点到rear的值复制到新生成的后半部分
        if (rear<front){
            for (int i=0;i<=rear;i++){
                array[i+initCapacity]=this.array[i];
                array[i]= Integer.parseInt(null);
            }
            rear=rear+initCapacity;
        }
    }

    public void enQueue(int data){
        if (isFull()){
            resizeQueu();
        }
        rear=(rear+1)%capacity;
        array[rear]=data;
        //如果栈还未添加过元素
        if (front==-1){
            front=rear;
        }
    }
    public int deQueue() throws EmptyQueueException {
        int data= Integer.parseInt(null);
        if (isEmpty()){
            throw new EmptyQueueException("Queue Empty");
        }else {
            data= array[front];
            //如果只有一个元素
            if (front==rear){
                front=rear=-1;
            }else {
                front=(front+1)%capacity;
            }
        }
        return data;
    }

    private class EmptyQueueException extends Throwable {
        public EmptyQueueException(String queue_empty) {
            System.out.println(queue_empty);
        }

        @Override
        public void printStackTrace() {
            System.out.println("Queue Empty");
        }
    }
}
